Broadband integrated service digital networks (B-ISDN) provide end-to-end transport for a broad spectrum of services flexibly and efficiently via the asynchronous transfer mode (ATM) technique. Information is packetized and carried in fixed length "cells." Each cell consists of 53 octets including 5-octet header and 48-octet information fields. Due to the natural random-ness of the broadband traffic, queues are required at various placed in ATM networks to absorb instantaneous traffic bursts that may exceed the network bandwidth temporarily.
Various architectures for ATM switches, also called fast packet switches, have been proposed. Among them, switches with output queues (including shared output buffers) have been proven to give the best delay/throughput performance.
FIG. 1 shows a prior art ATM switch fabric with output queues which I have previously proposed and which is an improved version of a prior art knockout switch. It is capable of accommodating more than 8,000 input ports to achieve a Terabit/sec throughput. Cell filtering and contention resolution functions are performed in parallel in small switch elements (SWE) , located at the intersection of cross-bar lines.
The SWE examine incoming cells from horizontal lines and route them properly to one of the L links of each output port. The L can be chosen as 12 in order to have less than 10.sup.-10 cell probability caused by contention among the L routing links. The ATM switch fabric will route higher priority cells to output ports when congestion occurs among the L routing links. At any given cell time slot (about 2.83 .mu.s) , if there is more than one cell arriving at an output port, all except one will be stored in the output queue waiting to be sent to the transmission link.
Under normal traffic conditions, most of the queued cells will be transmitted on the link and a simple first-in-first-out (FIFO) queue discipline will provide acceptable cell loss/delay performance. However, under congestion, a queue management algorithm is essential to discipline the queued cells in such a way that higher priority cells will always be sent to the outputs before the lower priority ones, the low priority cells will be dropped when the queue is full, and within the same priority any interference on others' reserved network resources is prevented by setting up some policies and disciplines (or firewalls).
Since different traffic has different service requirements, real-time traffic such as video and voice should be assigned high priorities to satisfy its stringent delay requirements while data traffic may be handled at lower priorities tolerating longer delay. A simple FIFO queue won't be able to handle the prioritized cells nor prevent the interference of one connection with another.
For instance, consider a situation in which a conventional FIFO is used for each output queue of the switch as shown in FIG. 1. When long cell bursts from a misbehaving user are queued up in the FIFO, the other regular arrival cells will be delayed or even dropped when the FIFO is full.
Round-robin disciplines are believed able to provide fairer service than the FIFO discipline when the network is congested. Their throughput/delay performance comparison can be found in the article entitled "Queuing Disciplines And Passive Congestion Control In Byte-Stream Networks" by S.P. Morgan, IEEE INFOCOM '89, 1989, pp. 711-720. The round-robin discipline usually operates by maintaining a separate FIFO queue for each connection, which is identified by a 2-octet VCI (virtual channel identifier) in each cell header. The queues are visited in a cyclic order and thus, when congestion occurs, light-traffic and short-burst users are protected by evenly cutting back all user's throughput to approximately the same level.
Three hardware implementations for the round-robin discipline were presented in the article entitled "Fast Switching And Fair Control Of Congested Flow In Broadband Networks" by M. G. H. Katevenis, IEEE J. Select Areas Commun., Vol. 5, No. 8, pp. 1315-11325, Oct. 1987. However, their hardware complexity increases as either the number of connections (VCIS) or priority levels increase. Especially, as the number of VCIs approaches 64K, the hardware circuitry grows considerably to the point that per VCI processing speed limitation may become the system's bottleneck. Furthermore, each connection may request different transmission rates at the initial call set up and thus the round-robin discipline may not serve all users "fairly" in the sense that every user shares the remaining resource equally, rather than sharing the resource proportionally to the transmission rates that they have requested.